Discrete Mathematics
Q71.
G is undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.Q72.
Consider the following directed graph: The number of different topological orderings of the vertices of the graph isQ73.
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.Q74.
A cube of side 1 unit is placed in such a way that the origin coincides with one of its top vertices and the three axes along three of its edges. What are the co-ordinates of the vertex which is diagonally opposite to the vertex whose co-ordinates are (1, 0, 1)?Q75.
If G is a forest with n vertices and k connected components, how many edges does G have?Q77.
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?Q78.
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,f):1\leqi\leq12, 1\leqj\leq12}. There is an edge between (a,b) and (c,d) if |a-c|\leq1 and |b-d| \leq1. The number of edges in the graph is ____.Q80.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?